/**
 * 34. Find First And Last Position Of Element In Sorted Array
 * https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/
 */
class FindFirstAndLastPositionOfElementInSortedArray {
    public int[] searchRange(int[] nums, int target) {
        int start = lowerBound(nums, target);
        if (start == nums.length || nums[start] != target) {
            return new int[]{-1, -1};
        }
        int end = lowerBound(nums, target + 1) - 1;
        return new int[]{start, end};
    }

    /**
     * 方法： lowerBound
     * 逻辑: 查找第一个大于等于目标值的位置
     * Args:
     * - nums: int[] - 已排序的整数数组
     * - target: int - 目标值
     * Returns:
     * - int - 第一个大于等于目标值的位置
     * Time:
     * - O(log n) - 二分查找的时间复杂度
     * Space:
     * - O(1) - 只使用了常数级的额外空间
     */
    public int lowerBound(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1; // 闭区间 [left, right]
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] >= target) {
                right = mid - 1; // 缩小范围到[left, mid-1]
            } else {
                left = mid + 1; //缩小范围到[mid+1, left]
            }
        }
        // 循环结束后 left = right + 1
        // 此时 nums[left -1] < target 而 nums[left] = nums[right+1] >=target
        // 所以left就是第一个>=target的元素下标
        return left;
    }

}